'''
@author: Kevin Zhao
@data:Jan 4,2012 
@note:
Selection algorithm:selection in worst-case linear time
http://en.wikipedia.org/wiki/Selection_algorithm


Exercise 9.3-0
Linear general selection algorithm - Median of Medians algorithm
'''
import math
from c2 import partial_insertion_sort

def exchange(A_index, B_index, array):
    temp = array[A_index]
    array[A_index] = array[B_index]
    array[B_index] = temp
def partition(A, p, r):
    i = p - 1
    for j in range(p, r):
        if A[j] <= A[r]:
            i += 1
            exchange(i, j, A)
    exchange(r, i + 1, A)
    return i + 1

def find_median_index(A, p, r):
    if p == r:
        return p
    partial_insertion_sort(A, p, r)
    return int(math.floor((r - p) / 2)) + p
'''
Iterative version of randomized selection algorithm
Input:Array-A,startIndex:p,endIndex:r,the ith order of the desired element
output:the desired element at ith order of the array
'''
def selection(A, p, r, i):
    array_size = r - p + 1
    if i < 0 or i > len(A):
        print "WARNING:randomized_selection_iterative(A, p, r, >i<)   i should be in range 1<=i<=N"
        return 
    if p == r:
        return p
    '0.If the amount of elements is less than five,just use insertion sort instead'
    if array_size <= 5:
        partial_insertion_sort(A, p, r + 1)
        return p + i - 1
    '1.Divide'
    group_count = int(math.floor(array_size / 5))
    '2.Find the medians'
    '2.1 Group the sub-array'
    for j in range(0, group_count):
        median_index = selection(A, p + j * 5, p + j * 5 + 4, 2)
        'put the median into a continuous area at the beginning of the sub-array'
        exchange(median_index, p + j, A)
    '2.2 Group the remaining elements into a group'
    if len(A) > group_count * 5:
        left = p + group_count * 5
        right = len(A) - 1
        mid = int(math.ceil((float(right) - left) / 2))
        median_index = selection(A, left , right , mid)
        'put the median into a continuous area at the beginning of the sub-array'
        exchange(median_index, p + group_count, A)
        group_count += 1
    '3.Find the median of medians(all the medians are located at the beginning of the sub-array)'
    final_median_index = selection(A, p, p + group_count, int(math.ceil(float(group_count) / 2)))
    '4.Partition around the pivot element'
    exchange(final_median_index, r, A)
    q = partition(A, p, r)
    '5.Doing selection recursively'
    k = q - p + 1
    if i == k:
        return q
    elif i < k:
        r = q - 1
        return selection(A, p, r, i)
    else:
        p = q + 1
        i = i - k
        return selection(A, p, r, i)
            
A = [13, 19, 9, 5, 12, 8, 7, 4, 21, 2, 6, 11]
p = 0
r = len(A) - 1
i = 1
#print('\n'.join(sorted(sys.path)))
print A[selection(A, p, r, 1)]
print A[selection(A, p, r, 2)]
print A[selection(A, p, r, 3)]
print A[selection(A, p, r, 4)]
print A[selection(A, p, r, 5)]
print A[selection(A, p, r, 6)]
print A[selection(A, p, r, 7)]
print A[selection(A, p, r, 8)]
print A[selection(A, p, r, 9)]
print A[selection(A, p, r, 10)]
print A[selection(A, p, r, 11)]
print A[selection(A, p, r, 12)]
print A[selection(A, p, r, 13)]


            
            
            
